过去我们一直在求单源最短路,今天让我们看一下多源最短路的求法。我们介绍一下它的核心思想:即不断在原有基础上添加新的中转点并求出此时的最优状态,是一种动态规划思想的体现。具体流程:我们先列出无中转点(也就是相邻的点)间的dis;然后枚举中转点k(有点类似区间dp),转移方程为f[i][j](从i到j)=min(f[i][j],f[i][k]+f[k][j]).正确性证明:当我们先枚举a为中转时,我们就可以求得任意两点之间经过与不经过a的最短距离。当我们先枚举b为中转时,我们就可以求得任意两点之间经过a与b的排列组合(不大准确,可以选一个,也可以都不选)(也就是ab与ba,a,b,0)同理,当我们
797.所有可能的路径题目:给你一个有n个节点的有向无环图(DAG),请你找出所有从节点0到节点n-1的路径并输出(不要求按特定顺序)graph[i]是一个从节点i可以访问的所有节点的列表(即从节点i到节点graph[i][j]存在一条有向边)。示例1:输入:graph=[[1,2],[3],[3],[]]输出:[[0,1,3],[0,2,3]]解释:有两条路径0->1->3和0->2->3示例2:输入:graph=[[4,3,1],[3,2,4],[3],[4],[]]输出:[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]答案classSolutio